package com.example.leetcode.matrix.common;

import com.example.leetcode.graph.common.unionfind.twodimension.UnionFind;
import javafx.util.Pair;

import java.util.*;

public class MatrixUtils {
    public static void printMatrix(int[][] matrix) {
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public static void setZeroes(int[][] matrix) {

        int m = matrix.length;
        int n = matrix[0].length;

        boolean[] rows = new boolean[m];
        boolean[] columns = new boolean[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    columns[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            if (rows[i]) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (columns[i]) {
                for (int j = 0; j < m; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
    }

    public static int[][] flipAndInvertImage(int[][] image) {
        int m = image.length;
        int n = image[0].length;
        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = 1 - image[i][n - 1 - j];
            }
        }
        return result;
    }

    public static int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] result = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[i][j] = matrix[j][i];
            }
        }
        return result;
    }

    public static int[][] sortTheStudents(int[][] score, int k) {
        Arrays.sort(score, (o1, o2) -> o2[k] - o1[k]);
        return score;
    }

    public static boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j || (i + j) == (n - 1)) {
                    if (grid[i][j] == 0) {
                        return false;
                    }
                } else if (grid[i][j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    public static int[] findColumnWidth(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[] ans = new int[col];
        for (int j = 0; j < col; j++) {
            int maxWidth = 0;
            // 遍历每一列
            for (int[] ints : grid) {
                // 此处优化了，感谢大佬指点，String.valueOf对负数也是可以的
                int width = String.valueOf(ints[j]).length();
                if (width > maxWidth) {
                    maxWidth = width;
                }
            }
            ans[j] = maxWidth;
        }
        return ans;
    }

    public static int[] rowAndMaximumOnes(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0; i < row; i++) {
            int count = 0;
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == 1) {
                    count++;
                }
            }
            if (count > max) {
                max = count;
            }
            map.put(i, count);
        }
        int index = -1;
        for (Integer key : map.keySet()) {
            if (map.get(key) == max) {
                if (index == -1) {
                    index = key;
                } else {
                    if (key < index) {
                        index = key;
                    }
                }
            }
        }
        return new int[]{index, max};
    }

    public static int findMaxFish(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        boolean[][] visited = new boolean[row][col];
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        int[] x = {0, 0, 1, -1};
        int[] y = {1, -1, 0, 0};
        int ans = 0;
        while (true) {
            int startX = -1;
            int startY = -1;
            // 查找起点
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] > 0 && !visited[i][j]) {
                        startX = i;
                        startY = j;
                        break;
                    }
                }
                if (startX != -1) {
                    break;
                }
            }
            // 如果不存在合法的起点
            if (startX == -1) {
                break;
            }
            // 遍历这个起点周边的水域
            Pair<Integer, Integer> node = new Pair<>(startX, startY);
            visited[startX][startY] = true;
            queue.add(node);
            int curRes = 0;
            while (queue.size() > 0) {
                Pair<Integer, Integer> curNode = queue.poll();
                int curX = curNode.getKey();
                int curY = curNode.getValue();
                curRes += grid[curX][curY];
                for (int i = 0; i < 4; i++) {
                    int newX = curX + x[i];
                    int newY = curY + y[i];
                    if (newX >= 0 && newX < row
                            && newY >= 0 && newY < col
                            && !visited[newX][newY]
                            && grid[newX][newY] > 0
                    ) {
                        Pair<Integer, Integer> newNode = new Pair<>(newX, newY);
                        queue.add(newNode);
                        visited[newX][newY] = true;
                    }
                }
            }
            // 更新答案
            ans = Math.max(ans, curRes);
        }
        return ans;
    }

    public static int firstCompleteIndex(int[] arr, int[][] mat) {
        Map<Integer, Integer> rowMap = new HashMap<>();
        Map<Integer, Integer> colMap = new HashMap<>();
        int m = mat.length;
        int n = mat[0].length;
        for (int i = 0; i < m; i++) {
            rowMap.put(i, n);
        }
        for (int i = 0; i < n; i++) {
            colMap.put(i, m);
        }
        Map<Integer, Pair<Integer, Integer>> matrix = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Pair<Integer, Integer> node = new Pair<>(i, j);
                matrix.put(mat[i][j], node);
            }
        }
        for (int i = 0; i < arr.length; i++) {
            Pair<Integer, Integer> node = matrix.get(arr[i]);
            int row = node.getKey();
            int col = node.getValue();
            rowMap.merge(row, -1, Integer::sum);
            if (rowMap.get(row) == 0) {
                return i;
            }
            colMap.merge(col, -1, Integer::sum);
            if (colMap.get(col) == 0) {
                return i;
            }
        }
        return -1;
    }

    public static int minimumCost(int[] start, int[] target, int[][] specialRoads) {


        return 0;
    }

    public static int[][] matrixRankTransform(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        UnionFind uf = new UnionFind(m, n);
        for (int i = 0; i < m; i++) {
            Map<Integer, List<int[]>> num2indexList = new HashMap<>();
            for (int j = 0; j < n; j++) {
                int num = matrix[i][j];
                num2indexList.putIfAbsent(num, new ArrayList<>());
                num2indexList.get(num).add(new int[]{i, j});
            }
            for (List<int[]> indexList : num2indexList.values()) {
                int[] arr1 = indexList.get(0);
                int i1 = arr1[0], j1 = arr1[1];
                for (int k = 1; k < indexList.size(); k++) {
                    int[] arr2 = indexList.get(k);
                    int i2 = arr2[0], j2 = arr2[1];
                    uf.union(i1, j1, i2, j2);
                }
            }
        }
        for (int j = 0; j < n; j++) {
            Map<Integer, List<int[]>> num2indexList = new HashMap<>();
            for (int i = 0; i < m; i++) {
                int num = matrix[i][j];
                num2indexList.putIfAbsent(num, new ArrayList<>());
                num2indexList.get(num).add(new int[]{i, j});
            }
            for (List<int[]> indexList : num2indexList.values()) {
                int[] arr1 = indexList.get(0);
                int i1 = arr1[0], j1 = arr1[1];
                for (int k = 1; k < indexList.size(); k++) {
                    int[] arr2 = indexList.get(k);
                    int i2 = arr2[0], j2 = arr2[1];
                    uf.union(i1, j1, i2, j2);
                }
            }
        }

        int[][] degree = new int[m][n];
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int i = 0; i < m; i++) {
            Map<Integer, int[]> num2index = new HashMap<>();
            for (int j = 0; j < n; j++) {
                int num = matrix[i][j];
                num2index.put(num, new int[]{i, j});
            }
            List<Integer> sortedArray = new ArrayList<>(num2index.keySet());
            Collections.sort(sortedArray);
            for (int k = 1; k < sortedArray.size(); k++) {
                int[] prev = num2index.get(sortedArray.get(k - 1));
                int[] curr = num2index.get(sortedArray.get(k));
                int i1 = prev[0], j1 = prev[1], i2 = curr[0], j2 = curr[1];
                int[] root1 = uf.find(i1, j1);
                int[] root2 = uf.find(i2, j2);
                int ri1 = root1[0], rj1 = root1[1], ri2 = root2[0], rj2 = root2[1];
                degree[ri2][rj2]++;
                adj.putIfAbsent(ri1 * n + rj1, new ArrayList<int[]>());
                adj.get(ri1 * n + rj1).add(new int[]{ri2, rj2});
            }
        }
        for (int j = 0; j < n; j++) {
            Map<Integer, int[]> num2index = new HashMap<>();
            for (int i = 0; i < m; i++) {
                int num = matrix[i][j];
                num2index.put(num, new int[]{i, j});
            }
            List<Integer> sortedArray = new ArrayList<>(num2index.keySet());
            Collections.sort(sortedArray);
            for (int k = 1; k < sortedArray.size(); k++) {
                int[] prev = num2index.get(sortedArray.get(k - 1));
                int[] curr = num2index.get(sortedArray.get(k));
                int i1 = prev[0], j1 = prev[1], i2 = curr[0], j2 = curr[1];
                int[] root1 = uf.find(i1, j1);
                int[] root2 = uf.find(i2, j2);
                int ri1 = root1[0], rj1 = root1[1], ri2 = root2[0], rj2 = root2[1];
                degree[ri2][rj2]++;
                adj.putIfAbsent(ri1 * n + rj1, new ArrayList<int[]>());
                adj.get(ri1 * n + rj1).add(new int[]{ri2, rj2});
            }
        }

        Set<Integer> rootSet = new HashSet<>();
        int[][] ranks = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int[] rootArr = uf.find(i, j);
                int ri = rootArr[0], rj = rootArr[1];
                rootSet.add(ri * n + rj);
                ranks[ri][rj] = 1;
            }
        }
        Queue<int[]> queue = new ArrayDeque<>();
        for (int val : rootSet) {
            if (degree[val / n][val % n] == 0) {
                queue.offer(new int[]{val / n, val % n});
            }
        }
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int i = arr[0], j = arr[1];
            for (int[] adjArr : adj.getOrDefault(i * n + j, new ArrayList<int[]>())) {
                int ui = adjArr[0], uj = adjArr[1];
                degree[ui][uj]--;
                if (degree[ui][uj] == 0) {
                    queue.offer(new int[]{ui, uj});
                }
                ranks[ui][uj] = Math.max(ranks[ui][uj], ranks[i][j] + 1);
            }
        }
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int[] rootArr = uf.find(i, j);
                int ri = rootArr[0], rj = rootArr[1];
                res[i][j] = ranks[ri][rj];
            }
        }
        return res;
    }


    public static int matrixSum(int[][] nums) {
        int m = nums.length;
        int n = nums[0].length;
        List<PriorityQueue<Integer>> queueList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            queueList.add(new PriorityQueue<>((o1, o2) -> o2 - o1));
        }

        for (int i = 0; i < m; i++) {
            PriorityQueue<Integer> queue = queueList.get(i);
            for (int j = 0; j < n; j++) {
                queue.add(nums[i][j]);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            // 每一行选取一个最大的数删除
            for (int j = 0; j < m; j++) {
                priorityQueue.add(queueList.get(j).poll());
            }
            ans += priorityQueue.poll();
        }
        return ans;
    }

    public static class MatrixNode {
        public int x;
        public int y;
        public int startX;
        public int startY;
        public int topLeftSize;
        public int bottomRight;

        public MatrixNode(int x, int y, int startX, int startY, int topLeftSize, int bottomRight) {
            this.x = x;
            this.y = y;
            this.startX = startX;
            this.startY = startY;
            this.topLeftSize = topLeftSize;
            this.bottomRight = bottomRight;
        }
    }

    public static int[][] differenceOfDistinctValues(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        Map<Pair<Integer, Integer>, Set<Integer>> lineNumbers = new HashMap<>();
        MatrixNode[][] nodes = new MatrixNode[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (i == 0 || j == 0) {
                    lineNumbers.put(new Pair<>(i, j), new HashSet<>());
                    MatrixNode node = new MatrixNode(i, j, i, j, 0, 0);
                    nodes[i][j] = node;
                    continue;
                }
                MatrixNode node = new MatrixNode(i, j, nodes[i - 1][j - 1].startX, nodes[i - 1][j - 1].startY, 0, 0);
                Set<Integer> set = lineNumbers.get(new Pair<>(node.startX, node.startY));
                set.add(grid[i - 1][j - 1]);
                node.topLeftSize = set.size();
                nodes[i][j] = node;
            }
        }

        for (int i = row - 1; i >= 0; i--) {
            for (int j = col - 1; j >= 0; j--) {
                if (i == row - 1 || j == col - 1) {
                    lineNumbers.put(new Pair<>(i, j), new HashSet<>());
                    nodes[i][j].startX = i;
                    nodes[i][j].startY = j;
                    nodes[i][j].bottomRight = 0;
                    continue;
                }
                MatrixNode node = nodes[i][j];
                node.startX = nodes[i + 1][j + 1].startX;
                node.startY = nodes[i + 1][j + 1].startY;
                Set<Integer> set = lineNumbers.get(new Pair<>(node.startX, node.startY));
                set.add(grid[i + 1][j + 1]);
                node.bottomRight = set.size();
                nodes[i][j] = node;
            }
        }

        int[][] res = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                res[i][j] = Math.abs(nodes[i][j].topLeftSize - nodes[i][j].bottomRight);
            }
        }
        return res;
    }
}
